package com.atcumt.lcSolution;

public class LC9 {

    /*
     * 分割字符串的最大得分
     * 输入：s = "011101"
     * 输出：5
     */
    public int maxScore(String s) {
        int n = s.length();
        int score = s.charAt(0) == '0' ? 1 : 0;
        for (int i = 1; i < n; i++) {
            score += s.charAt(i) - '0';
        }
        int res = score;
        for (int i = 1; i < n - 1; i++) {
            if (s.charAt(i) == '0') {
                score += 1;
            } else {
                score -= 1;
            }
            res = Math.max(res, score);
        }
        return res;
    }

    /* 
     * 解码方法
     * dp[i]：以 s[i] 结尾的前缀子串有多少种解码方法
     * 类似斐波那契数列
     */
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            // 截取一个字符
            if (s.charAt(i - 1) != '0') {
                dp[i] = dp[i - 1];
            }
            // 截取两个字符
            if (i >= 2 && (s.charAt(i - 2) == '1' || s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6')) {
                dp[i] += dp[i -2];
            }
        }
        return dp[n];
    }
}
